/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 // https://leetcode-cn.com/problems/split-linked-list-in-parts/
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        // 如果链表为空，返回一个含有k个元素且每个元素都是nullptr的向量
        if(!root) return vector<ListNode *>(k, nullptr);
        ListNode *pos = root; // pos是一个工作指针
        int totalLen = 0;
        while(pos)
        {
            totalLen ++; // 算出链表的总长度
            pos = pos -> next;
        }
        int avgLen = totalLen / k; // 每段子链表的平均长度
        int remainder = totalLen % k; // 余数
        vector<ListNode *> result(k, nullptr);
        ListNode *head = root;
        ListNode *prev = nullptr;
        for(int i=0; i<k; ++i) // 外层循环定位到result的每一位
        {
            result[i] = head;
            int eachLen = remainder>0 ? (avgLen+1) : avgLen;
            for(int j=0; j<eachLen; ++j) // 内层循环处理result的每一位应该包含原始链表的哪些元素
            {
                prev = head;
                head = head -> next;
            } 
            prev -> next = nullptr; // result[i]已处理完，将其与原链表root断开
            remainder -- ;
        }
        return result;
    }
};